//
// Created by Dinger on 2021/9/18.
//
#include"..//Header files//conversion_form.h"


ConversionForm::ConversionForm() {
    _row = 0;
    _col = 0;
    _letterFlag = false;
    _isDFA = true;
}

ConversionForm::ConversionForm(string fileName, bool letterFlag) {
    _row = 0;
    _col = 0;
    _letterFlag = letterFlag;
    _isDFA = true;
    readFile(fileName);
    minimizeDFA();
    writeInFile("..//test_MINI_form.txt");
}

ConversionForm::ConversionForm(string fileName, bool letterFlag, bool isDFA) {
    _row = 0;
    _col = 0;
    _letterFlag = letterFlag;
    _isDFA = isDFA;
    if (isDFA) {
        //将转换表读入文件
        readFile(fileName);
        //对DFA最小化
        minimizeDFA();
    } else {
        //将NFA转换表读入文件
        readFileNFA(fileName);
        //确定化
        NFA2DFA();
        //最小化
        //minimizeDFA();
        //写进文件

    }
    writeInFile("..//test_DFA_form.txt");
}

void ConversionForm::readFile(string fileName) {
    ifstream codeFile1(fileName);
    string readWord;
    vector<int> oneRow;
    if (!codeFile1.is_open()) {
        cout << "Error opening file";
        exit(1);
    }
    int col = 0;
    char ch;
    while ((ch = codeFile1.get()) != '\n') {
        if (ch == '\t' || ch == ' ') {
            continue;
        }
        _symbols.push_back(ch);
    }
    _col = _symbols.size();
    while (codeFile1 >> readWord) {
        col++;
        if (col == 1) {
            _states.push_back(findStates(readWord));
            continue;
        }
        oneRow.push_back(atoi(readWord.c_str()));
        if (col == _col + 1) {
            col = 0;
            _conversionForm.push_back(oneRow);
            oneRow.clear();
            _row++;
        }
    }
}

int ConversionForm::findSymbolPosition(char symbol) {
    if (!_isDFA) {
        _symbols = _symbolsNFA;
    }
    if (symbol == '\n') {
        symbol = '\\';
    } else if (symbol == ' ') {
        symbol = '^';
    }
    for (int i = 0; i < _symbols.size(); i++) {
        if (_letterFlag) {
            if ((symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) {
                if (_symbols[i] == 'l') {
                    return i;
                }
            } else if (symbol == _symbols[i]) {
                return i;
            }
        } else if (symbol == _symbols[i]) {
            return i;
        }
    }
    return 24;
}

void ConversionForm::readFileNFA(string fileName) {
    ifstream codeFile1(fileName);
    string readWord;
    vector<vector<int>> oneRow;
    if (!codeFile1.is_open()) {
        cout << "Error opening file";
        exit(1);
    }
    int col = 0;
    char ch;
    while ((ch = codeFile1.get()) != '\n') {
        if (ch == '\t' || ch == ' ') {
            continue;
        }
        _symbolsNFA.push_back(ch);
    }
    _col = _symbolsNFA.size();
    while (codeFile1 >> readWord) {
        col++;
        if (col == 1) {
            _statesNFA.push_back(findStates(readWord));
            continue;
        }
        oneRow.push_back(divideStates(readWord));
        if (col == _col + 1) {
            col = 0;
            _conversionFormNFA.push_back(oneRow);
            oneRow.clear();
            _row++;
        }
    }
    _spacePosition = findSymbolPosition('?');
    if (_spacePosition != -1) {
        _symbols = vector<char>(_symbolsNFA.begin(), _symbolsNFA.end() - 1);
    }
}

vector<int> ConversionForm::divideStates(string inputString) {
    if (inputString.empty()) {
        return vector<int>();
    }
    if (inputString == "-1") {
        return vector<int>(1, -1);
    }
    string numberString;
    vector<int> states;
    for (int i = 0; i < inputString.size(); i++) {
        if (inputString[i] == ',') {
            states.push_back(atoi(numberString.c_str()));
            numberString.clear();
            continue;
        }
        if (inputString[i] < '0') {
            continue;
        }
        if (inputString[i] > '9') {
            continue;
        }
        numberString.push_back(inputString[i]);
    }
    states.push_back(atoi(numberString.c_str()));
    return states;
}

void ConversionForm::NFA2DFA() {
    vector<int> oneRow;
    vector<bool> tags(1, false);
    //单个状态的闭包
    set<int> closure;
    //所有状态闭包集合
    vector<set<int>> allClosures;
    //先找状态0的闭包
    findClosure(0, closure);
    allClosures.push_back(closure);
    //找未标记的状态下标（若有多个取第一个）
    int noMarkedState = findNoMarkedState(tags);
    int k = 0;
    _states.push_back(k);
    while (noMarkedState >= 0) {
        //标记该状态
        tags[noMarkedState] = true;
        //提取该闭包
        closure = allClosures[noMarkedState];
        for (int i = 0; i < _symbolsNFA.size() - 1; i++) {
            //求新的闭包
            set<int> newClosure = findClosure(findMove(closure, _symbolsNFA[i]));
            //在闭包集合中找新闭包
            int findNumber = findClosureInAllClosures(newClosure, allClosures);
            //如果没找到
            if (findNumber == -1) {
                k++;
                //新状态加入k
                _states.push_back(k);
                //找新的终态
                findNewTerminalState(newClosure, k);
                //闭包集合中加入新闭包
                allClosures.push_back(newClosure);
                //闭包flag集合加入false
                tags.push_back(false);
                //新的转换表中，该行加入k
                oneRow.push_back(k);
            } else {
                //新的转换表中，该行加入findNumber
                oneRow.push_back(findNumber);
            }
        }
        //新的转换表中加入该行
        _conversionForm.push_back(oneRow);
        oneRow.clear();
        noMarkedState = findNoMarkedState(tags);
    }
}

int ConversionForm::findStates(string inputString) {//输入文件找出状态集合
    if (inputString.empty()) {
        return 0;
    }
    string numberString;

    for (int i = 0; i < inputString.size(); i++) {
        if (inputString[i] < '0') {
            continue;
        }
        if (inputString[i] > '9') {
            continue;
        }
        numberString += inputString[i];
    }
    int number = atoi(numberString.c_str());
    if (inputString[inputString.size() - 1] == '#') {
        if (_isDFA) {
            _terminalStates.push_back(number);
        } else {
            _terminalStatesNFA.push_back(number);
        }
    }
    return number;
}

int ConversionForm::findNoMarkedState(vector<bool> tags) {
    for (int i = 0; i < tags.size(); i++) {
        if (tags[i]) {
            continue;
        }
        return i;
    }
    return -1;
}

set<int> ConversionForm::findClosure(set<int> states) {//查找每个状态对应的空边闭包
    set<int> totalClosure;
    set<int> initClosure;
    for (set<int>::iterator it = states.begin(); it != states.end(); it++) {
        findClosure((*it), initClosure);
        totalClosure.insert(initClosure.begin(), initClosure.end());
    }
    return totalClosure;
}

void ConversionForm::findClosure(int state, set<int> &closure) {//查找单个状态对应的空边闭包
    closure.insert(state);
    vector<int> states = _conversionFormNFA[state][_spacePosition];
    if (states.size() == 1 && states[0] == -1) {
        return;
    }
    for (int i = 0; i < states.size(); i++) {
        set<int> closure1, closure2;
        findClosure(states[i], closure);
    }
}

set<int> ConversionForm::findMove(set<int> closure, char symbol) {
    set<int> totalClosure;
    for (set<int>::iterator it = closure.begin(); it != closure.end(); it++) {
        vector<int> states = _conversionFormNFA[(*it)][findSymbolPosition(symbol)];
        if (states[0] != -1) {
            totalClosure.insert(states.begin(), states.end());
        }
    }
    return totalClosure;
}

int ConversionForm::findClosureInAllClosures(set<int> closure, vector<set<int>> allClosures) {/在所有闭包中搜索某个闭包
    for (int i = 0; i < allClosures.size(); i++) {
        if (isEqual(allClosures[i], closure)) {
            return i;
        }
    }
    return -1;
}

bool ConversionForm::isEqual(set<int> closure1, set<int> closure2) {
    map<set<int>, int> compareMap;
    compareMap[closure1] = 1;
    if (compareMap.find(closure2) != compareMap.end()) {
        return true;
    }
    return false;
}

void ConversionForm::writeInFile(string fileName) {
    ofstream codeFile1(fileName);
    string readWord;
    char ch;
    int size = (_isDFA ? _symbols.size() : _symbols.size() - 1);
    for (int i = 0; i < size; i++) {
        codeFile1 << "\t" << _symbols[i];
    }
    for (int i = 0; i < _conversionForm.size(); i++) {
        codeFile1 << endl << _states[i];
        if (isTerminal(_states[i])) {
            codeFile1 << '#';
        }
        for (int j = 0; j < _conversionForm[i].size(); j++) {
            codeFile1 << "\t" << _conversionForm[i][j];
        }
    }
    codeFile1.close();
}

void ConversionForm::findNewTerminalState(set<int> closure, int k) {//查找闭包中是否含有终结状态
    for (int i = 0; i < _terminalStatesNFA.size(); i++) {
        if (closure.find(_terminalStatesNFA[i]) != closure.end()) {
            _terminalStates.push_back(k);
            return;
        }
    }
}

bool ConversionForm::isTerminal(int state) {//查看该状态是否是终结的
    for (int i = 0; i < _terminalStates.size(); i++) {
        if (state == _terminalStates[i]) {
            return true;
        }
    }
    return false;
}

void ConversionForm::minimizeDFA() {
    vector<int> unTerminalStates;
    for (int i = 0; i < _states.size(); i++) {
        if (isTerminal(_states[i])) {
            continue;
        }
        unTerminalStates.push_back(_states[i]);
    }
    vector<vector<int>> statesGroups{unTerminalStates, _terminalStates};//非终结部分和终结部分
    int statesGroupNumber = 0;
    for (int i = 0; i < _symbols.size(); i++) {
        //递归调用该函数，不断分割状态组
        minimizeProcess(statesGroups, statesGroupNumber, i);
        statesGroupNumber = 0;
    }
    remakeForm(statesGroups);
}

void ConversionForm::minimizeProcess(vector<vector<int>> &statesGroups, int &statesGroupNumber, int symbolNumber) {
    vector<vector<int>> newStatesGroups;
    bool judgeClassify = false;
    if (statesGroupNumber >= statesGroups.size()) {
        return;
    }
    if (symbolNumber >= _symbols.size()) {
        return;
    }
    vector<int> oneGroup = statesGroups[statesGroupNumber];
    vector<vector<int>> otherGroups = findOtherGroups(statesGroups, statesGroupNumber);
    vector<vector<int>> resultStatesGroups;
    //在一个条件下分割一个状态组
    bool flag = classifyStatesInOneSymbol(statesGroups, oneGroup, otherGroups,
                                          resultStatesGroups, _symbols[symbolNumber]);
    newStatesGroups.insert(newStatesGroups.end(), resultStatesGroups.begin(),
                           resultStatesGroups.end());
    newStatesGroups.insert(newStatesGroups.end(), otherGroups.begin(), otherGroups.end());
    statesGroups = newStatesGroups;
    if (!flag) {
        statesGroupNumber++;
    }
    minimizeProcess(statesGroups, statesGroupNumber, symbolNumber);
}

bool ConversionForm::isInStates(vector<int> states, int state) {
    for (int i = 0; i < states.size(); i++) {
        if (state == states[i]) {
            return true;
        }
    }
    return false;
}

bool ConversionForm::classifyStatesInOneSymbol(vector<vector<int>> statesGroups, vector<int> oneStatesGroup,
                                               vector<vector<int>> otherGroups, vector<vector<int>> &resultStatesGroups,
                                               char symbol) {
    int symbolPosition = findSymbolPosition(symbol);//查看输入字符在表中的位置
    vector<vector<int>> groups(statesGroups.size() + 1);//定义新的状态集合
    for (int i = 0; i < oneStatesGroup.size(); i++) {
        int state = oneStatesGroup[i];
        int nextState = _conversionForm[state - 1][symbolPosition];
        if (nextState == -1) {//判断状态对应的输入的值是否是空的
            groups[0].push_back(state);
            continue;
        }
        for (int j = 0; j < statesGroups.size(); j++) {
            if (isInStates(statesGroups[j], nextState)) {//如果nextState在stateGroups的中新的状态集合不变
                groups[j + 1].push_back(state);
                break;
            }
        }
    }
    for (int i = 0; i < groups.size(); i++) {
        if (groups[i].empty()) {
            continue;
        }
        resultStatesGroups.push_back(groups[i]);
    }
    if (resultStatesGroups.size() > 1) {
        return true;
    }
    return false;
}

vector<vector<int>> ConversionForm::findOtherGroups(vector<vector<int>> statesGroups, int i) {
    vector<vector<int>> resultGroups;
    for (int j = 0; j < statesGroups.size(); j++) {
        if (j == i) {
            continue;
        }
        resultGroups.push_back(statesGroups[j]);
    }
    return resultGroups;
}

void ConversionForm::remakeForm(vector<vector<int>> statesGroups) {//构造新的转换表
    map<int, vector<int>> statesMap;
    map<int, int> newStateMap = makeNewStateMap(statesGroups);
    vector<vector<int>> newForm;
    vector<int> newState;
    vector<int> newTerminalStates;
    set<int> terminalStates;
    int size = 0;
    for (int i = 0; i < _conversionForm.size(); i++) {
        vector<int> oneRow;
        if (_states[i] != newStateMap[_states[i]]) {
            continue;
        }
        newState.push_back(_states[i]);
        for (int j = 0; j < _conversionForm[i].size(); j++) {
            oneRow.push_back(newStateMap[_conversionForm[i][j]]);
        }
        newForm.push_back(oneRow);
    }
    for (int i = 0; i < _terminalStates.size(); i++) {
        terminalStates.insert(newStateMap[_terminalStates[i]]);
        if (size != terminalStates.size()) {
            newTerminalStates.push_back(newStateMap[_terminalStates[i]]);
            size = terminalStates.size();
        }
    }
    _terminalStates = newTerminalStates;
    _conversionForm = newForm;
    _states = newState;
}

map<int, int> ConversionForm::makeNewStateMap(vector<vector<int>> statesGroups) {
    map<int, int> newMap;
    for (int i = 0; i < statesGroups.size(); i++) {
        for (int j = 0; j < statesGroups[i].size(); j++) {
            newMap.insert(pair<int, int>(statesGroups[i][j], statesGroups[i][0]));
        }
    }
    newMap.insert(pair<int, int>(-1, -1));
    return newMap;
}